#include "markov-predictor.h"

//因为第一个版本的markov并没有限制没有个桶元素数量，所以在实际的使用中出现的运行效率过低的情况
//在这里我们对于每一个桶使用LRU的策略，当一个节点被访问之后，我们就使用LRU的策略将这个节点放到头部
//所以我们需要严格限定一个节点和一个历史数量，并且使用LRU的淘汰策略
//那么何时提升一个节点的优先级就是一个问题了，这里我们在计数变化的时候更新历史后继记录优先级
//以及在其被搜索的时候提升元数据节点的优先级

//这里我们认定，history记录我们通过LRU的策略保留最近的5个，每个桶的基本节点的元数据我们通过LRU的策略保留最近的100个
//并且我们设定10000个桶
//789116
//一个元数据块的新数据的初始化
void init_markov_block_meta_item(markov_block_meta_item_t* markov_block_meta_item, long block_num){
    
    memset(markov_block_meta_item, 0, sizeof(markov_block_meta_item_t));

    markov_block_meta_item->block_num = block_num;
    markov_block_meta_item->size = 0;
    
    //将计数链表打个结，头部节点全指向自己
    //为历史的计数节点的申请一个头部节点
    markov_block_meta_item->head = (markov_block_successor_counter_item_t *)malloc(sizeof(markov_block_successor_counter_item_t));
    memset(markov_block_meta_item->head, 0, sizeof(markov_block_successor_counter_item_t));

    markov_block_meta_item->head->front = markov_block_meta_item->head;
    markov_block_meta_item->head->next = markov_block_meta_item->head;

    markov_block_meta_item->head->count = -1;
    markov_block_meta_item->head->block_num = -1;
    markov_block_meta_item->head->successor_num = -1;

    //以上是历史计数的头结点初始化
}


//初始化一个函数初始化整个预测器
void init_markov_block_meta(markov_block_predictor_t* markov_block_meta){

    printf("初始化markov预测器\n");

    int i;
    markov_block_meta_item_t* markov_block_meta_item;

    memset(markov_block_meta, 0, sizeof(markov_block_predictor_t));
    
    //这里首先初始化每一个桶，每个桶都是双向链表的head节点
    for(i = 0; i < MAX_MARKOV_BARREL_NUM; i++){
        //将一个人桶的头结点取出来
        markov_block_meta_item = &(markov_block_meta->block_metas[i]);
        //初始化头结点
        memset(markov_block_meta_item, 0, sizeof(markov_block_meta_item_t));

        //将指针指向自身
        markov_block_meta_item->front = markov_block_meta_item;
        markov_block_meta_item->next = markov_block_meta_item;
        
        markov_block_meta_item->block_num = -1;

        //头结点没有后继的记录
        markov_block_meta_item->head = NULL;
        //头结点的size不需要
        markov_block_meta_item->size = -1;
    }

    //初始化更多的属性
    //将历史节点打个结
    //申请一个历史链表的头部节点的空间
    markov_block_meta->history_head = (markov_history_meta_item_t *)malloc(sizeof(markov_history_meta_item_t));

    markov_block_meta->history_head->next = markov_block_meta->history_head;
    markov_block_meta->history_head->front = markov_block_meta->history_head;
}

//向一个桶中加入一个新节点，第三个形参为这个桶对应的大小
markov_block_meta_item_t* markov_add_new_item_in_barrel(markov_block_meta_item_t* block_meta_head, long block_num, long* barrel_size){
    
    
    //在头部插入新节点
    markov_block_meta_item_t* head_next = block_meta_head->next;
    markov_block_meta_item_t* del_block = block_meta_head->front;

    // if(markov_get_barrel_from_block(block_num)==5832){
    //     printf("当前访问的桶5832\n\n\n\n\n\n\n\n\n\n\n");    
    //     //看看指针是不是正常回环
    //     printf("打印当前的回环%ld\n",head_next->block_num);
    // }
    
    //申请一个新节点
    markov_block_meta_item_t* newItem = (markov_block_meta_item_t *)malloc(sizeof(markov_block_meta_item_t));
    memset(newItem, 0,  sizeof(markov_block_meta_item_t));

    //初始化这个新节点
    init_markov_block_meta_item(newItem, block_num);

    //将新节点放在桶的头部
    newItem->next = head_next;
    head_next->front = newItem;

    block_meta_head->next = newItem;
    newItem->front = block_meta_head;
    
    (*barrel_size)++;

    if((*barrel_size) > MAX_MARKOV_BARREL_SIZE){
        // if(del_block->block_num == 789116){
        //     printf("正在删除789116!!!!!!!!!!!!!!!\n");
        // }else{
        //     printf("正在删除%ld\n", del_block->block_num);
        // }

        //一个桶满了，从一个桶中的最后一个节点删除元素
        del_block->front->next = del_block->next;
        del_block->next->front = del_block->front;
        
        // printf("不应该来这里%ld\n", *barrel_size);

        free(del_block);
        del_block = NULL;

        (*barrel_size)--;
    }

    //返回插入的节点的指针
    return newItem;
}

//向一个节点中加一个历史后继,加一个新节点，
void markov_add_new_success_history(markov_block_meta_item_t* target_block, long history){
    //现在当前的块中寻找对应的节点，看看在不在
    markov_block_successor_counter_item_t* history_scan = target_block->head->next;
    markov_block_successor_counter_item_t* head_next;
    markov_block_successor_counter_item_t* head = target_block->head;
    markov_block_successor_counter_item_t* new_history_item;

    while(history_scan != target_block->head){
        if(history_scan->successor_num == history){
            //这里自增计数
            (history_scan->count)++;

            //将当前位置缝合一下
            history_scan->front->next = history_scan->next;
            history_scan->next->front = history_scan->front;

            //将当前节点放在头部
            head = target_block->head;
            head_next = target_block->head->next;

            head->next = history_scan;
            history_scan->front = head;

            head_next->front = history_scan;
            history_scan->next = head_next;
            return;
        }

        history_scan = history_scan->next;
    }

    //这里需要在头部新建并且插入一个新的节点
    new_history_item = (markov_block_successor_counter_item_t *)malloc(sizeof(markov_block_successor_counter_item_t));
    memset(new_history_item, 0, sizeof(markov_block_successor_counter_item_t));
    new_history_item->block_num = target_block->block_num;
    new_history_item->count = 1;
    new_history_item->successor_num = history;

    head_next = target_block->head->next;
    //这里重新连一下指针
    new_history_item->next = head_next;
    head_next->front = new_history_item;

    target_block->head->next = new_history_item;
    new_history_item->front = target_block->head;

    //在元数据块中增加一下历史后继的数量
    (target_block->size)++;

    //如果数量过大，那么就删除结尾的元素
    if(target_block->size > MAX_MARKOV_EACH_HISTORY_DEEP){
        //删除结尾的元素
        markov_block_successor_counter_item_t* del_history = head->front;
        
        //将删除的前后节点缝合
        del_history->next->front = del_history->front;
        del_history->front->next = del_history->next;

        free(del_history);
        del_history = NULL;

        (target_block->size)--;
    }
}

//这里创建一个函数从一个桶中搜索一个元素
markov_block_meta_item_t* markov_search_block_meta_in_barrel(markov_block_meta_item_t* barrel_head, long block_num){

    markov_block_meta_item_t* block_scan = barrel_head->next;
    markov_block_meta_item_t* barrel_head_next;

    while(block_scan != barrel_head){
        // printf("当前搜索节点%ld，当前访问节点%ld\n", block_num,block_scan->block_num);
        if(block_scan->block_num == block_num){
            
            //这里将当前节点前后缝合一下
            block_scan->front->next = block_scan->next;
            block_scan->next->front = block_scan->front;

            barrel_head_next = barrel_head->next;

            //这里将找到的节点放在桶的头部
            block_scan->front = barrel_head;
            barrel_head->next = block_scan;
            
            block_scan->next = barrel_head_next;
            barrel_head_next->front = block_scan;

            // if(block_num == 3175832){
            //     //打印几位看看情况
            //     printf("这里看看在更新优先级之后的情况\n");
            //     printf("%ld\n", barrel_head->block_num);
            //     printf("%ld\n", barrel_head->next->block_num);
            //     printf("%ld\n", barrel_head->next->next->block_num);
            //     printf("%ld\n", barrel_head->next->next->next->block_num);
            //     exit(0);
            // } 
            //返回当前搜到的
            return block_scan;
        }
        block_scan = block_scan->next;
    }

    return NULL;
}

//为一个block分配对应的一个桶
int markov_get_barrel_from_block(long block_num){
    //用取模的方式来返回桶的号码
    //我们将头结点-1也要考虑在内
    if(block_num == -1){
        return 0;
    }

    return block_num % MAX_MARKOV_BARREL_NUM;
}

//我们向历史后继计数块中做一个减操作，在一个节点的历史后继节点，做一次自减操作
//如果减到0，那就删除这个节点
void markov_del_old_success_history(markov_block_meta_item_t* target_block, long history, long* barrel_size){
    markov_block_successor_counter_item_t* history_scan = target_block->head->next;
    markov_block_successor_counter_item_t* history_head_next;
    markov_block_successor_counter_item_t* history_head = target_block->head;

    markov_block_successor_counter_item_t* history_scan_front;
    markov_block_successor_counter_item_t* history_scan_next;

    //进行一下搜索操作
    while(history_scan != target_block->head){
        if(history_scan->successor_num == history){
            //这里做一个自减
            (history_scan->count)--;
            if(history_scan->count == 0){
                //将这个历史节点删除
                history_scan_front = history_scan->front;
                history_scan_next = history_scan->next;

                //前后两个节点连接到一起
                history_scan_front->next = history_scan_next;
                history_scan_next->front = history_scan_front;

                //释放当前扫描到的节点
                free(history_scan);
                history_scan=NULL;
                //将历史后继记录大小减一
                (target_block->size)--;

                //当前节点已经没有后继了
                if(target_block->size == 0){
                    //在桶中删除当前节点
                    target_block->front->next = target_block->next;
                    target_block->next->front = target_block->front;

                    //释放空间
                    free(target_block);

                    target_block=NULL;

                    //当前桶的大小减少
                    (*barrel_size)--;
                }

                //不用改变节点的优先级，这是在search的时候干的事情
            }else{
                //这里需要将当前节点放在历史节点头部
                //将这个历史节点删除
                history_scan_front = history_scan->front;
                history_scan_next = history_scan->next;

                //前后两个节点连接到一起
                history_scan_front->next = history_scan_next;
                history_scan_next->front = history_scan_front;
                
                history_head_next = history_head->next;

                //将当前节点放在头部
                history_head->next = history_scan;
                history_scan->front = history_head;

                history_head_next->front = history_scan;
                history_scan->next = history_head_next;
            }
            //这里就处理完了，退出函数
            return;
        }

        history_scan = history_scan->next;
    }

    //到这里说明没有搜到，这是没有关系的事情
    
}

//向历史记录中添加一个元素，传入要添加的元素，返回的是可可能弹出的元素
markov_history_meta_item_t markov_add_history(markov_history_meta_item_t* history_head, long block_num, long history, long* history_size){
    markov_history_meta_item_t* newItem;
    markov_history_meta_item_t* history_head_next;
    markov_history_meta_item_t* return_history_meta_next;
    markov_history_meta_item_t* return_history_meta_front;
    markov_history_meta_item_t* return_history_meta;
    markov_history_meta_item_t return_history;

    return_history.target_block = -1;
    
    //新建元素
    newItem = (markov_history_meta_item_t *)malloc(sizeof(markov_history_meta_item_t));
    memset(newItem, 0, sizeof(markov_history_meta_item_t));


    newItem->target_block = block_num;
    newItem->success_block = history;

    //首先在头部插入元素
    history_head_next = history_head->next;

    history_head->next = newItem;
    newItem->front = history_head;

    history_head_next->front = newItem;
    newItem->next = history_head_next;

    //更新大小
    (*history_size)++;

    //如果大小太大了就返回末尾的元素
    if((*history_size) > MAX_MARKOV_HISTORY_SIZE){
        return_history_meta = history_head->front;
        return_history_meta_front = return_history_meta->front;
        return_history_meta_next = return_history_meta->next;

        //将两个历史记录块缝合上
        return_history_meta_front->next = return_history_meta_next;
        return_history_meta_next->front = return_history_meta_front;

        //自减
        (*history_size)--;

        return_history = *return_history_meta;

        free(return_history_meta);
        //将关键的块返回
        return return_history;
    }

    //如果没有东西踢出，那就返回空指针
    return return_history;
}


//用一个函数来寻找一个节点的历史后继计数最大值
//如果没有最大值返回-1
long markov_find_max_successor(markov_block_meta_item_t* target_block){
    if(target_block == NULL){
        printf("找不到\n");
        return -1;
    }

    //用一个变量来存储最大值，用一个变量来存储最大值的出现的次数，还要一个变量来存储出现最多的块号
    int max = 0;
    long max_block;
    int max_count = 0;

    //用一个指针来扫描所有的历史数据
    markov_block_successor_counter_item_t* success_scan = target_block->head->next;

    //进行扫描
    while(success_scan != target_block->head){
        if(success_scan->count > max){
            max_block = success_scan->block_num;
            max = success_scan->count;
            max_count = 1;
        }
        if(success_scan->count == max){
            max_count++;
        }
        success_scan = success_scan->next;
    }

    //全部遍历完之后
    if(max_count == 1){
        //这里返回最大值
        return max_block;
    }

    printf("不能预测max_count=%d\n", max_count);

    //这里返回-1代表没有唯一最大值
    return -1;
}


//正式进行预测的函数，传入几个东西，一个是当前的预测器，一个是返回的序列，一个是返回序列的大小，最后一个是当前访问的地址
void markov_predictor(markov_block_predictor_t* block_predictor, long* return_arr, int* size, long now_access){
    
    
    printf("开始运行markov预测器，now_access = %ld\n", now_access);

    long last_access;
    markov_history_meta_item_t* history_scan;
    markov_history_meta_item_t* history_new_item;
    markov_history_meta_item_t history_del_item;
    markov_block_meta_item_t* block_meta_insert;
    markov_block_meta_item_t* block_meta_delete;
    markov_block_meta_item_t* block_meta_get_prediction;

    long now_predict;
    long predict_result;
    int i;
    int barrel_num;

    //然后更新，元数据的后继计数，即转化矩阵。
    //首先先计算出对应的桶，
    // if(now_access == 13829117){
    //     printf("当前访问的是%ld，属于的桶是%d\n", now_access, barrel_num);
    // }

    // printf("打印当前桶的大小%ld\n", block_predictor->size[barrel_num]);
    
    *size = 0;
    //首先查看上一次访问的节点，这个会记录在历史记录链表的第一位，如果找不到就不进行下面的事情
    history_scan = block_predictor->history_head->next;
    last_access = history_scan->success_block;

    barrel_num = markov_get_barrel_from_block(last_access);
    
    history_del_item = markov_add_history(block_predictor->history_head, last_access, now_access, &(block_predictor->history_size));
    // printf("添加了新的节点\n");

    //在对应的桶中先找到对应的元素
    block_meta_insert = markov_search_block_meta_in_barrel(&(block_predictor->block_metas[barrel_num]), last_access);
    // printf("找到了对应的元素\n");
    //看看有没有这个元素，如果有的话就新建一个元素
    if(block_meta_insert == NULL){
        // printf("打印当前桶的大小%ld\n", block_predictor->size[barrel_num]);
        block_meta_insert = markov_add_new_item_in_barrel(&(block_predictor->block_metas[barrel_num]), last_access, &(block_predictor->size[barrel_num]));
    }

    //插入新的元素
    markov_add_new_success_history(block_meta_insert, now_access);

    // printf("添加了新的后继\n");
    //查看弹出的历史记录
    //根据弹出的历史记录处理更新转化矩阵
    if(history_del_item.target_block == -1){
        // printf("有历史节点需要删除\n");
        
        //这里说明要修改元数据
        //讲道理对应的元数据对应的块应该是在的
        //找到删除块所占的桶
        barrel_num = markov_get_barrel_from_block(history_del_item.target_block);

        //在对应的桶中找到对应的元素
        block_meta_delete = markov_search_block_meta_in_barrel(&(block_predictor->block_metas[barrel_num]), history_del_item.target_block);

        //如果还可以找到这个节点，那就去删除这个节点的后继
        if(block_meta_delete != NULL){
            markov_del_old_success_history(block_meta_delete, history_del_item.success_block, &(block_predictor->size[barrel_num]));
        }
    }
    
    //根据greedy的策略获取最近的最可能的6位元素，如果有权重相同的最大，那就不进行预测
    //这里首先进行预测，从access_now为第一位开始，默认预测6位
    now_predict = now_access;
    
    // printf("开始预测\n");
    for(i = 0; i < MARKOV_PREDICTOR_DEEP; i++){
        //首先预测第一位
        //查看第一位所在的桶
        barrel_num = markov_get_barrel_from_block(now_predict);
        //然后我们把这个节点找出来
        // printf("找出节点\n");
        // printf("查找新元素%ld，查找元素的所在桶%d，新元素的桶大小%ld\n", now_predict, barrel_num,block_predictor->size[barrel_num]);

        
        //看看桶里面是什么
        // if(now_predict == 2735832){
        //     //看看桶中的内容
            
        // }
        block_meta_get_prediction = markov_search_block_meta_in_barrel(&(block_predictor->block_metas[barrel_num]), now_predict);

        //查看什么时候被修改了
    // markov_block_meta_item_t *barrel_head_ptr = &(block_predictor->block_metas[5832]);

    // printf("%ld\n", barrel_head_ptr->block_num);
    // printf("%ld\n", barrel_head_ptr->next->block_num);
    // printf("%ld\n", barrel_head_ptr->next->next->block_num);
    // printf("%ld\n", barrel_head_ptr->next->next->next->block_num);

        //在这个节点上，我们找出一个历史后继出现最多的节点
        // printf("找到预测值\n");
        predict_result = markov_find_max_successor(block_meta_get_prediction);

        //看看预测出来的是不是-1
        if(predict_result == -1){
            //并没法做出预测，结束当前预测
            break;
        }

        //这里说明可以做出预测
        return_arr[(*size)] = predict_result;
        (*size)++;

        now_predict = predict_result;
    }
}